/**
 * 
 */
package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName   : Leetcode051 
 * @author      : ganwei 
 * @date        : 2020年5月5日
 * @Description : Leetcode051 N皇后
 */
public class Leetcode0051 {
	//存储结果
	private List<List<String>> result = new ArrayList<>();
	// row
	int rows[];
	// "hill" diagonals
	int hills[];
	// "dale" diagonals
    int dales[];
    // queens positions
    int queens[];
    
    int n;
	
    /**
     * 当前情况下，是否可以放入皇后
     */
    public boolean isNotUnderAttack(int row, int col) {
    	System.out.println(row+" : "+col);
        int res = rows[col] + dales[row - col + n - 1] + hills[row + col];
        return (res == 0) ? true : false;
      }

    /**
     * 将皇后放置棋盘row行、col列
     */
    public void placeQueen(int row, int col){
    	queens[row] = col;
    	rows[col] = 1;
    	hills[row+col] = 1;
    	dales[row-col+n-1]=1;
    }
    /**
     * 将皇后从row行、col列移除
     */
    public void removeQueen(int row, int col){
    	queens[row] = 0;
    	rows[col] = 0;
    	hills[row+col] = 0;
    	dales[row-col+n-1]=0;
    }
    
    
	/**
	 * -解题思路，回溯(递归)算法
	 */
    public List<List<String>> solveNQueens(int n) {
    	this.n = n;
        rows = new int[n];
        hills = new int[4 * n - 1];
        dales = new int[2 * n - 1];
        queens = new int[n];

        backtrack(0);
    	
    	return result;
    }
    /**
     * -根据queens[]数组放置
     */
    public void addSolution(){
    	List<String> solution = new ArrayList<String>();
        for (int i = 0; i < this.n; ++i) {
            int col = queens[i];
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < col; ++j) sb.append(".");
            sb.append("Q");
            for(int j = 0; j < this.n - col - 1; ++j) sb.append(".");
            solution.add(sb.toString());
          }
          result.add(solution);

    }
    /**
     * -回溯函数
     */
    public void backtrack(int row){
    	if(row == n){
    		addSolution();
    		return;
    	}
    	for(int i = 0; i < this.n; i++){
    		if(!isNotUnderAttack(row,i)){
    			continue;
    		}
    		placeQueen(row,i);
    		backtrack(row+1);
    		removeQueen(row,i);
    	}
    }
    
    /*
    for (int col = 0; col < n; col++) {
      if (isNotUnderAttack(row, col)) {
        placeQueen(row, col);
        // if n queens are already placed
        if (row + 1 == n) addSolution();
          // if not proceed to place the rest
        else backtrack(row + 1);
        // backtrack
        removeQueen(row, col);
      }
    }
    */
    /**
     * -主函数
     */
    public static void main(String[] args){
    	Leetcode0051 l051 = new Leetcode0051();
    	l051.solveNQueens(4);
    }
    
    
}
